import heapq

def dij(s):

    q=[]
    dis[s]=0
    # 节点s的 (距离，节点)
    heapq.heappush(q,(0,s))
    while q:
        cnt,u=heapq.heappop(q)
        if cnt!=dis[u]:
            continue
        for v,w in mp[u]:
            # 从u到v的时间 + 在v隔离的时间 = 到v点的最短路径
            if dis[u]+w+a[v]<dis[v]:
                dis[v]=dis[u]+w+a[v]
                heapq.heappush(q,(dis[v],v))

n,m=map(int,input().split())
# 隔离时间
a=[0]+list(map(int,input().split()))
# 第一个城市 和 最后一个 不需要隔离
a[0]=a[n]=0
INF=float('inf')
mp=[[] for _ in range(n+1)]
# 到某点的最短路径的距离
dis=[INF]*(n+1)
for i in range(m):
    u,v,c=map(int,input().split())
    # 无向图
    mp[u].append((v,c))
    mp[v].append((u,c))
dij(1)
print(dis[n])

